//
// Created by wdq on 22-9-16.
//
//
// Created by wdq on 22-9-16.
//
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

struct Edge {
    int head;
    int tail;
    int weight;

    Edge() = default;

    Edge(int head, int tail, int weight) : head(head), tail(tail), weight(weight) {}


};


struct ALGraph {

    vector<Edge *> *edges;
    int edgeNum;
    int vexNum;
    const char *names;

    explicit ALGraph(const char *names) {
        this->edgeNum = 0;
        this->vexNum = int(strlen(names));
        this->names = names;
        this->edges = new vector<Edge *>();

    }

    void addArc(int head, int tail, int weight = 0) const {
        edges->emplace_back(new Edge(head, tail, weight));
    }

    void output() const {
        for (auto &i: *edges) {
            cout << names[i->head] << " -> " << names[i->tail] << endl;
        }
    }

    void output(Edge *edge) const {
        cout << names[edge->head] << " -> " << names[edge->tail] << " : " << edge->weight << endl;
    }
};

int findZeroDegree(vector<int> &degree) {
    for (int i = 0; i < degree.size(); i++) {
        if (degree[i] == 0) {
            return i;
        }

    }
    return -1;

}

void topSort(ALGraph &G) {
    vector<int> degree(G.vexNum);
    stack<int> topStack;
    vector<int> res;
    for (auto &i: *G.edges) {
        degree[i->tail]++;
    }
    int first = findZeroDegree(degree);
    if (first == -1) {
        cout << "there is a loop way!" << endl;
        return;
    }
    topStack.push(first);
    while (!topStack.empty()) {
        int temp = topStack.top();
        res.emplace_back(temp);
        topStack.pop();
        for (auto &i: *G.edges) {
            if (i->head == temp) {
                if (--degree[i->tail] == 0) {
                    topStack.push(i->tail);
                }
            }

        }
    }
    if (int(res.size()) == G.vexNum) {
        for (auto &i: res) {
            cout << "v" << G.names[i] << " -> ";
        }
        cout << endl;
        return;

    }
    cout << "there is a loop way" << endl;
}


int main() {
    const char *p = "123456789";
    ALGraph g(p);
    g.addArc(0, 1);
    g.addArc(0, 3);
    g.addArc(0, 2);
    g.addArc(1, 4);
    g.addArc(2, 4);
    g.addArc(3, 5);
    g.addArc(4, 6);
    g.addArc(4, 7);
    g.addArc(5, 7);
    g.addArc(6, 8);
    g.addArc(7, 8);
//    g.output();

    cout << "topSort: " << endl;
    topSort(g);


    return 0;
}